package com.yan_jiu_sheng.daily.AC;

/**
 * https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/description/?envType=daily-question&envId=2024-08-05
 * 参考题解:https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/solutions/990719/bu-han-lian-xu-1de-fei-fu-zheng-shu-by-l-9l86
 * 数位DP
 *
 * @author yulongtian
 * @create 2024-08-05 10:35
 */
public class Test20240805 {
    public static void main(String[] args) {

    }

    /**
     * 长度为n的二进制数字中不含连续1的非负整数个数满足斐波那契数列。
     * dp[n] = dp[n - 2] + dp[n - 1]
     * 该递推式表示长度为n的字符串，都可以通过以下两种方式获得：
     * 在长度为n-2的字符串左侧加10；
     * 在长度为n-1的字符串左侧加0。
     * 可以看到这个递推式就是斐波那契生成式
     * <p>
     * dp0=1
     * dp1=2
     * dp2=3
     * <p>
     * <p>
     * n=1  2
     * n=2  3
     * n=3  5
     *
     * @param n
     * @return
     */
    public int findIntegers(int n) {
        int[] dp = new int[31];
        dp[0] = dp[1] = 1;
        for (int i = 2; i < 31; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        int pre = 0, res = 0;
        for (int i = 29; i >= 0; --i) {
            int val = 1 << i;
            if ((n & val) != 0) {
                res += dp[i + 1];
                if (pre == 1) {
                    break;
                }
                pre = 1;
            } else {
                pre = 0;
            }

            if (i == 0) {
                ++res;
            }
        }

        return res;
    }

}
